﻿using System;
using System.Collections.Generic;
using STeaL.Functional;

namespace STeaL.Algorithm {
  public static partial class IListExtensions {
#region partition
    public static int partition<T>(this IList<T> list, int first, int last, Func<T,bool> pred) {
      for ( ; ; ++first ) {
        for ( ; first != last && pred(list[first]); ++first ) ;
        if ( first == last ) break;
        for ( ; first != --last && !pred(list[last]); ) ;
        if ( first == last ) break;
        iter_swap(list, first, last);
      }
      return first;
    }

    public static int partition<T>(this IList<T> list, Func<T,bool> pred) {
      return partition(list, 0, list.Count, pred);
    }

#endregion
#region stable_partition
    public static int stable_partition<T>(this IList<T> list, int first, int last, Func<T,bool> pred ) {
      int pos = 0;
      int mid = first;
      if ( first != last ) {
        T[] buf = new T[last-first];
        for ( ; first != last; ++first ) {
          if ( pred(list[first]) ) {
            list[mid++] = list[first];
          } else {
            buf[pos++] = list[first];
          }
        }
        pos = 0;
        for ( first =mid; first != last; ++first ) {
          list[first] = buf[pos++];
        }
      }
      return mid;
    }

    public static int stable_partition<T>(this IList<T> list, Func<T,bool> pred ) {
      return stable_partition(list, 0, list.Count, pred);
    }

#endregion
#region is_partitioned
    public static bool is_partitioned<T>(this IList<T> list, int first, int last, Func<T,bool> pred) {
      for ( ; first != last; ++first )
        if ( !pred(list[first]) ) break;
      for ( ; first != last; ++first )
        if ( pred(list[first]) ) return false;
      return true;
    }

    public static bool is_partitioned<T>(this IList<T> list, Func<T,bool> pred) {
      return is_partitioned(list, 0, list.Count, pred);
    }

#endregion
#region partition_point
    public static int partition_point<T>(this IList<T> list, int first, int last, Func<T,bool> pred) {
      for (; first != last; ++first)
       if ( !pred(list[first]) ) break;
      return first;
    }

    public static int partition_point<T>(this IList<T> list, Func<T,bool> pred) {
      return partition_point(list, 0, list.Count, pred);
    }

#endregion
  }
}
